package simpledb;

/** A class to represent a fixed-width histogram over a single integer-based field.
 * int类型字段的直方图
 * 用于记录每个值区间的元组个数
 */
public class IntHistogram {

    /**
     * Create a new IntHistogram.
     * 
     * This IntHistogram should maintain a histogram of integer values that it receives.
     * It should split the histogram into "buckets" buckets.
     * 
     * The values that are being histogrammed will be provided one-at-a-time through the "addValue()" function.
     * 
     * Your implementation should use space and have execution time that are both
     * constant with respect to the number of values being histogrammed.  For example, you shouldn't 
     * simply store every value that you see in a sorted list.
     * 
     * @param buckets The number of buckets to split the input value into.
     * @param min The minimum integer value that will ever be passed to this class for histogramming
     * @param max The maximum integer value that will ever be passed to this class for histogramming
     *            histogram直方图数组   索引表示的int值的区间
     *            width：直方图索引代表的区间
     *            min:最小值
     *            max：最大值
     *            buckets：直方图记录的索引个数
     *            ntups：元组个数
     *            由于int值可能会过大，如果直接用直方图存储每一个int值导致空间浪费
     *            所以设定一个buckets值作为直方图的bin个数，每个bin代表一段区间width
     */
    private int[] histogram;
    private int width;
    private int min;
    private int max;
    private int buckets;
    private int ntups ;
    public IntHistogram(int buckets, int min, int max) {
    	// some code goes here
        this.buckets = buckets;
        this.min = min;
        this.max = max;
        //可能buckets大于max-min，此时width为1
        double range = (max-min)*1.0/buckets*1.0;
        this.width = (int) Math.ceil(range);
        this.histogram = new int[buckets];
        this.ntups = 0;
    }

    /**
     * Add a value to the set of values that you are keeping a histogram of.
     * @param v Value to add to the histogram
     *          每扫描到一个元组的对应字段
     *          直方图对应的索引代表的元组个数加一
     */
    public void addValue(int v) {
    	// some code goes here
        int index = val2index(v);
        histogram[index]++;
        ntups++;
    }
    /**
    将字段值转换为直方图的索引
     */
    private int val2index(int val)
    {
        if(val==max)
        {
            return buckets-1;
        }
        int index = (int)(val-min)/width;
        return index;
    }


    /**
     * Estimate the selectivity of a particular predicate and operand on this table.
     * 
     * For example, if "op" is "GREATER_THAN" and "v" is 5, 
     * return your estimate of the fraction of elements that are greater than 5.
     * 
     * @param op Operator
     * @param v Value
     * @return Predicted selectivity of this particular operator and value
     * 给定一个值v和一个操作符op
     * 计算op v在直方图中的个数占所有元组的比例
     * 例如计算  >5这一个条件过滤之后所剩的元组比例  就计算在直方图的大于5的所占的元组数/总元组个数
     */
    public double estimateSelectivity(Predicate.Op op, int v) {
        int index = val2index(v);
        // some code goes here
        int height = 0;
        int left = 0;
        int right = 0;
        double s1 = 0;
        double s2 = 0;
        switch(op){
            case GREATER_THAN:
                if(v>=max)
                    return 0;
                if(v<min)
                    return 1;
                height = histogram[index];
                left = v;
                right = min+(index+1)*width;
                //由于直方图的一个bucket表示一个区间所占的元组数，所以需要计算在一个区间内的元组数
                //如区间5-10 要计算>7的话需要计算7-10所占的比例。简单起见就用 histogram[i]/width平均作为一个val的元组数
                s1 = (height*(right-left-1)/width*1.0)*(1.0/ntups);
                int allright = 0;
                for (int i = index+1; i<buckets ; i++) {
                    allright+=histogram[i];
                }
                s2 = allright*1.0/ntups;
                return s1+s2;
            case LESS_THAN:
                if(v>max)
                    return 1;
                if(v<=min)
                    return 0;
                height = histogram[index];
                left = min+index*width;
                right = v;
                s1 = (height*(right-left-1)/width*1.0)*(1.0/ntups);
                int allleft = 0;
                for (int i = index-1; i >0 ; i--) {
                   allleft+=histogram[i];
                }
                s2 = allleft*1.0/ntups;
                return s1+s2;
            case EQUALS:
                if(v>max||v<min)
                    return 0;
                return histogram[index]*1.0/width/ntups;
            case GREATER_THAN_OR_EQ:
                return estimateSelectivity(Predicate.Op.EQUALS,v)+estimateSelectivity(Predicate.Op.GREATER_THAN,v);
            case LESS_THAN_OR_EQ:
                return estimateSelectivity(Predicate.Op.EQUALS,v)+estimateSelectivity(Predicate.Op.LESS_THAN,v);
            case NOT_EQUALS:
                return 1-estimateSelectivity(Predicate.Op.EQUALS,v);
        }
        return 1.0;
    }
    
    /**
     * @return
     *     the average selectivity of this histogram.
     *     
     *     This is not an indispensable method to implement the basic
     *     join optimization. It may be needed if you want to
     *     implement a more efficient optimization
     * */
    public double avgSelectivity()
    {
        // some code goes here
        return 1.0;
    }
    
    /**
     * @return A string describing this histogram, for debugging purposes
     */
    public String toString() {
        // some code goes here
        return histogram.toString();
    }
}
